package util;

/**
 * @Classname TreeNode
 * @Description kektree node
 * @Date
 * @Created by kevin
 */

import accessstruct.Tool;
import it.unisa.dia.gas.jpbc.Element;
import it.unisa.dia.gas.jpbc.Pairing;
import it.unisa.dia.gas.plaf.jpbc.pairing.PairingFactory;

import java.util.*;

import util.ConfigFileName;
public class TreeUtil {
    /**
     * 返回树中节点个数
     *
     * @param root
     * @return
     */
    public static int getTreeNodeNum(TreeNode root) {
        if (root.getLeftChild() == null && root.getRightChild() == null) {
            return 1;
        }
        return getTreeNodeNum(root.getLeftChild()) +
                getTreeNodeNum(root.getRightChild()) + 1;
    }

    /**
     * 返回叶子节点到树根的路径
     *
     * @param leaf
     * @return
     */
    public static List<TreeNode> getPath(TreeNode leaf) {
        if (leaf == null) {
            return null;
        }
        List<TreeNode> pathNodeList = new ArrayList<TreeNode>();
        TreeNode TempNode = leaf;
        while (TempNode.getParent() != null) {
            pathNodeList.add(TempNode);
            TempNode = TempNode.getParent();
        }
        pathNodeList.add(TempNode);
        return pathNodeList;
    }

    /**
     * 获得最小覆盖集
     *
     * @param BT
     * @param revokeList 撤销列表
     * @return
     */
    public static List<TreeNode> KUNNodes(List<TreeNode> BT, List<TreeNode> revokeList) {

        List<TreeNode> X = new ArrayList<TreeNode>();
        List<TreeNode> Y = new ArrayList<TreeNode>();

        for (TreeNode treeNode : revokeList) {
            X.addAll(getPath(treeNode));
        }
        for (TreeNode treeNode : X) {
            if (treeNode.getLeftChild() != null && !X.contains(treeNode.getLeftChild())) {
                Y.add(treeNode.getLeftChild());
            }
            if (treeNode.getRightChild() != null && !X.contains(treeNode.getRightChild())) {
                Y.add(treeNode.getRightChild());
            }
        }
        if (Y.isEmpty())
            Y.add(BT.get(1));
        return Y;
    }

    /**
     * 创建包含n个叶子节点的树
     *
     * @param n
     * @return
     */
    public static List<TreeNode> createTree(int n, ConfigFileName config,Element g) {
        List<TreeNode> nodeList = new ArrayList<TreeNode>();
        Pairing bp = PairingFactory.getPairing(config.getPairingParametersFileName());
        Element xi = bp.getZr().newRandomElement().getImmutable();
        Element yi = g.powZn(xi).getImmutable();
        nodeList.add(new TreeNode( Integer.toString(0), xi, yi));//node0为占位节点
        int depth = (int) (Math.log(n) / Math.log(2)) + 1;
        for (int i = 1; i <= depth; i++) {
            for (int j = (int) (Math.pow(2, i - 1)); j < (int) (Math.pow(2, i)); j++) {
                Element xi_c = bp.getZr().newRandomElement().getImmutable();
                Element yi_c = g.powZn(xi_c).getImmutable();
                nodeList.add(new TreeNode( Integer.toString(j), xi_c, yi_c));
                nodeList.get(j).isLeaf = false;
                if (i == depth) {
                    nodeList.get(j).isLeaf = true;
                }
            }
        }
        for (int i = 1; i < nodeList.size(); i++) {
            if (i != 1)
                nodeList.get(i).setParent(nodeList.get(i / 2));
            if (!nodeList.get(i).isLeaf) {
                nodeList.get(i).setLeftChild(nodeList.get(2 * i));
                nodeList.get(i).setRightChild(nodeList.get(2 * i + 1));
            }
        }
        return nodeList;
    }
}
